package work.tree;

import work.TreeNode;

import java.util.Arrays;

public class Problem105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        int leftSize = indexOf(inorder, preorder[0]);
        int[] pre1 = Arrays.copyOfRange(preorder, 1, 1 + leftSize);
        int[] pre2 = Arrays.copyOfRange(preorder, 1 + leftSize, n);
        int[] in1 = Arrays.copyOfRange(inorder, 0, leftSize);
        int[] in2 = Arrays.copyOfRange(inorder, 1 + leftSize, n);
        //左子树的根节点
        TreeNode left = buildTree(pre1, in1);
        //右子树的根节点
        TreeNode right = buildTree(pre2, in2);
        return new TreeNode(preorder[0],left,right);

    }
    private int indexOf(int[] a, int x){
        int i ;
        for (i = 0; a[i] != x; i++);
        return i;
    }

    public static void main(String[] args) {
        int[] p = {3,9,20,15,7};
        int[] i = {9,3,15,20,7};
        Problem105 problem105 = new Problem105();
        problem105.buildTree(p,i);
    }
}
